home *** CD-ROM | disk | FTP | other *** search
/ Aminet 2 / Aminet AMIGA CDROM (1994)(Walnut Creek)[Feb 1994][W.O. 44790-1].iso / Aminet / misc / amag / sh9301c.lha / Differenzieren(S.91) / listing.c < prev    next >
C/C++ Source or Header  |  1992-10-24  |  9KB  |  459 lines
  1. /* Differenzieren eines mathematischen Ausdruckes */
  2. /* von Markus Öllinger */
  3.  
  4. #include <ctype.h>
  5. #include <string.h>
  6. #include <stdio.h>
  7. #include <stdlib.h>
  8.  
  9. typedef enum {OP_OPEN=-2,OP_CLOSE,OP_NONE=0,OP_ADD,OP_SUB,
  10.     OP_MUL,OP_DIV,OP_NEG,OP_POT,OP_FUNC1} OP;
  11.  
  12. struct Knoten {
  13.     struct Knoten *l,*r;
  14.     OP Operator;
  15.     short int Pri;
  16.     short int Len;
  17.     char *Term;
  18. };
  19.  
  20. struct Knoten *Neuer_Operand(char *cp,char **x);
  21. void verwende_Operator(OP);
  22. struct Knoten *Differenziere(struct Knoten *);
  23.  
  24. extern char *Funktion[];
  25.  
  26. OP operator_stack[1024];    /* Der Operator-Stapel */
  27. int sp_operator;    /* Sein Stapelzeiger */ 
  28. struct Knoten *operand_stack[1024];
  29. int sp_operand;
  30.  
  31. /* wandle Operatorenzeichen in Token um */
  32.  
  33. OP Operator(int op)
  34. {
  35.     switch(op) {
  36.         case '+': return OP_ADD;
  37.         case '-': return OP_SUB;
  38.         case '*': return OP_MUL;
  39.         case '/': return OP_DIV;
  40.         case '_': return OP_NEG;
  41.         case '^': return OP_POT;
  42.     }
  43.     return 0;
  44. }
  45.  
  46. /* bestimme Priorität des Operators */
  47.  
  48. Pri(OP op)
  49. {
  50.     switch(op) {
  51.         case OP_ADD:
  52.         case OP_SUB: return 1;
  53.         case OP_MUL:
  54.         case OP_DIV: return 2;
  55.         case OP_NEG: return 3;
  56.         case OP_POT: return 4;
  57.         case OP_NONE: return 0;
  58.         default: return 5;
  59.     }
  60. }
  61.  
  62. /* konstruiere Baum aus String */
  63.  
  64. struct Knoten *Baum_aufbauen(char *term)
  65. {
  66.     char *cp=term;
  67.     int i,l,pri,p;
  68.     OP op,op2;
  69.     char c;
  70.  
  71.     while((c=*cp)!=0) {
  72.         if(c=='(') operator_stack[sp_operator++]=OP_OPEN;
  73.         else if(isalnum(c)) {
  74.             if(isalpha(c)) {
  75.                 for(i=0;Funktion[i];i++)
  76.                     if(!strncmp(Funktion[i],cp,l=strlen(Funktion[i]))) {
  77.                         pri=5;
  78.                         op=OP_FUNC1+i;
  79.                         cp+=l-1;
  80.                         goto operator;
  81.                     }
  82.             }
  83.             operand_stack[sp_operand++]=Neuer_Operand(cp,&cp);
  84.             cp--;
  85.         }
  86.         else if(c==')')
  87.             for(;;) {
  88.                 if(!sp_operator) goto error;
  89.                 op=operator_stack[--sp_operator];
  90.                 if(op!=OP_OPEN) verwende_Operator(op);
  91.                 else break;
  92.             }
  93.         else {
  94.             op=Operator(c);
  95.             pri=Pri(op);
  96.  
  97.                 /* Subtraktion oder Negation? */
  98.  
  99.             if(op==OP_SUB && (cp==term || cp[-1]=='(')) {
  100.                 op=OP_NEG;
  101.                 pri=3;
  102.             }
  103. operator:    /* verwende alle Operatoren höherer Priorität */
  104.             while(sp_operator) {
  105.                 op2=operator_stack[sp_operator-1];
  106.                 p=Pri(op2);
  107.  
  108.             /* Prioritätsvergleich. Achtung ^ ist rechtsassoziativ */
  109.  
  110.                 if(op2==OP_OPEN || p<pri || p==pri && p==4)
  111.                     break;
  112.                 --sp_operator;
  113.                 verwende_Operator(op2);
  114.             }
  115.             operator_stack[sp_operator++]=op;
  116.         }
  117.         cp++;
  118.     }
  119.     while(sp_operator) {
  120.         op2=operator_stack[--sp_operator];
  121.         if(op2==OP_CLOSE) goto error;
  122.         verwende_Operator(op2);
  123.     }
  124.     if(sp_operand!=1) goto error;
  125.     return operand_stack[--sp_operand];
  126. error:
  127.     return NULL;
  128. }
  129.  
  130. /* gibt Baum wieder frei (rekursiv, wie alles) */
  131.  
  132. void Baum_abbauen(struct Knoten *k)
  133. {
  134.     if(k) {
  135.         if(k->l) Baum_abbauen(k->l);
  136.         if(k->r) Baum_abbauen(k->r);
  137.         free(k);
  138.     }
  139. }
  140.  
  141.     /* Hilfsroutinen */
  142.  
  143. struct Knoten *Neuer_Knoten(void)
  144. {
  145.     struct Knoten *k=malloc(sizeof(struct Knoten));
  146.     if(k==NULL) {
  147.         fprintf(stderr,"Speicher voll!\n");
  148.         exit(10);
  149.     }
  150.     memset((void *)k,0,sizeof(*k));
  151.     return k;
  152. }
  153.  
  154. struct Knoten *Neuer_Operand(char *cp,char **x)
  155. {
  156.     struct Knoten *k;
  157.     char *s;
  158.  
  159.     k=Neuer_Knoten();
  160.     s=cp;
  161.     while(*++s=='.' || isalnum(*s));
  162.     k->Term=cp;
  163.     k->Len=s-cp;
  164.     *x=s;
  165.     return k;
  166. }
  167.  
  168. char *Op(OP op)
  169. {
  170.     static char c[]={" +-*/-^"};
  171.  
  172.     if(op>=OP_FUNC1) return Funktion[op-OP_FUNC1];
  173.     return &c[op];
  174. }
  175.  
  176. struct Knoten *Neuer_Operator(OP op)
  177. {
  178. struct Knoten *k;
  179.  
  180.     k=Neuer_Knoten();
  181.     k->Operator=op;
  182.     k->Pri=Pri(op);
  183.     k->Term=Op(op);
  184.     k->Len=op>=OP_FUNC1?strlen(k->Term):1;
  185.     return k;
  186. }
  187.  
  188. /* holt ein od. zwei Operanden vom Operandenstapel
  189.  * und verknüpft sie mit dem angeg. Operator und
  190.  * legt Ergebnis wieder zurück.
  191.  */
  192.  
  193. void verwende_Operator(OP op)
  194. {
  195.     struct Knoten *k;
  196.     int p=Pri(op);
  197.  
  198.     k=Neuer_Operator(op);
  199.     k->r=operand_stack[--sp_operand];
  200.     switch(p) {
  201.         case 1:
  202.         case 2:
  203.         case 4:
  204.             k->l=operand_stack[--sp_operand];
  205.             k->Operator=op;
  206.             k->Pri=p;
  207.             break;
  208.     }
  209.     operand_stack[sp_operand++]=k;
  210. }
  211.  
  212. /* erzeugt eine Kopie des Baumes */
  213.  
  214. struct Knoten *BaumKopie(struct Knoten *k)
  215. {
  216.     struct Knoten *n=NULL;
  217.  
  218.     if(k) {
  219.         n=Neuer_Operator(OP_NONE);
  220.         *n=*k;
  221.         n->l=BaumKopie(k->l);
  222.         n->r=BaumKopie(k->r);
  223.     }
  224.     return n;
  225. }
  226.  
  227. /* Geht die in "Regel" gespeicherte Differenzierregel durch.
  228.  * Diese ist in Präfixform gespeichert und hat folgende Syntax:
  229.  * u entspricht dem linken Operanden (nicht differenziert)
  230.  * a entspricht dem linken Operanden (aber differenziert)
  231.  * v und b dasselbe rechts
  232.  * + - * / ^ entsprechen den jeweilgen Operatoren.
  233.  * _ entspricht dem (unären) Negationsoperator (Minus-Vorzeichen)
  234.  * #XX entspricht einer Funktion, XX gibt die Funktionsnummer an.
  235.  * #01 ist die Funktion mit dem im Feldelement Funktion[0]
  236.  * gespeicherten Namen (hier ln), #02 entspr. Funktion[1] usw.
  237.  * Eine Ziffer steht für die angegebene Zahl.
  238.  *
  239.  * in den globalen Variablen u, v, a und b werden die
  240.  * gleichnamigen Teilbäume erwartet.
  241.  */
  242.  
  243. char *Regel;    /*zu verwendende Regel*/
  244. struct Knoten *u,*v,*a,*b;
  245.  
  246. /* Hier sind sie: die Differenzierregeln für
  247.  * + - * / Negation und ^.
  248.  */
  249.  
  250. char *dRegeln[]={
  251.     NULL,"+ab","-ab","+*av*bu","/-*av*bu^v2",
  252.     "_b","*^uv+*b#01u*/vua"};
  253.  
  254. /* Die Funktionsnamen und die Regeln für die Ableitung */
  255.  
  256. char *Funktion[]={"ln","sinh","cosh","sin","cos",
  257.     "exp",NULL};
  258. char *dFunk[]={"/bv","*#03vb","*#02vb","*#05vb","*_#04vb",
  259.     "*#06vb"};
  260.  
  261. struct Knoten *Regeln(void)
  262. {
  263.     struct Knoten *k;
  264.     int d;
  265.  
  266.     switch(d=*Regel++) {
  267.         case 'a': k=BaumKopie(a);break;
  268.         case 'b': k=BaumKopie(b);break;
  269.         case 'u': k=BaumKopie(u);break;
  270.         case 'v': k=BaumKopie(v);break;
  271.         case '_': k=Neuer_Operator(OP_NEG);k->r=Regeln();break;
  272.         case '#':    /* Funktion */
  273.             sscanf(Regel,"%d",&d);
  274.             Regel+=2;
  275.             k=Neuer_Operator(d+OP_FUNC1-1);
  276.             k->r=Regeln();
  277.             break;
  278.         default:
  279.             if(isdigit(d)) {    /* Zahl */
  280.                 k=Neuer_Knoten();
  281.                 k->Term=Regel-1;
  282.                 k->Len=1;
  283.             } else {        /* Operator */
  284.                 k=Neuer_Operator(Operator(d));
  285.                 k->l=Regeln();
  286.                 k->r=Regeln();
  287.             }
  288.     }
  289.     return k;
  290. }
  291.  
  292. /* erledigt das Differenzieren mittels Rekursion */
  293.  
  294. struct Knoten *Differenziere(struct Knoten *k)
  295. {
  296.     static char One='1',Zero='0';
  297.     struct Knoten *d;
  298.  
  299.     if(k->Operator==OP_NONE) {        /* Blatt (Operand) */
  300.         d=Neuer_Knoten();
  301.         if(k->Len==1 && k->Term[0]=='x')
  302.             d->Term=&One;
  303.         else d->Term=&Zero;
  304.         d->Len=1;
  305.         return d;
  306.     }
  307.     if(k->Operator>=OP_FUNC1) {    /* Funktion */
  308.         b=Differenziere(k->r);
  309.         v=k->r;
  310.         Regel=dFunk[k->Operator-OP_FUNC1];
  311.         d=Regeln();
  312.         Baum_abbauen(b);
  313.         return d;
  314.     }
  315.  
  316.         /* Operator */
  317.  
  318.     if(k->l) d=Differenziere(k->l);
  319.     else d=NULL;
  320.     b=Differenziere(k->r);
  321.     a=d;
  322.     u=BaumKopie(k->l);
  323.     v=BaumKopie(k->r);
  324.     Regel=dRegeln[k->Operator];
  325.     d=Regeln();
  326.     Baum_abbauen(u);
  327.     Baum_abbauen(v);
  328.     Baum_abbauen(a);
  329.     Baum_abbauen(b);
  330.     return d;
  331. }
  332.  
  333.     /* Baum zurück in String umwandeln */
  334.  
  335. /* hat der Vater v einen Sohn s mit einem Operator
  336.  * niedrigerer Priorität?
  337.  */
  338.  
  339. pri_klammer(struct Knoten *v,struct Knoten *s,char **sp)
  340. {
  341.     if(v->Pri>s->Pri && s->Pri!=0 || v->Pri==s->Pri && v->Pri==4) {
  342.         (*sp)[0]='(';
  343.         (*sp)++;
  344.         return 1;
  345.     }
  346.     return 0;
  347. }
  348.  
  349. /* mach ev. Klammer wieder zu */
  350.  
  351. void klammer_zu(char **sp,int kl)
  352. {
  353.     if(kl) {
  354.         (*sp)[0]=')';
  355.         (*sp)++;
  356.     }
  357. }
  358.  
  359. void Baum_zu_String(struct Knoten *k,char *s)
  360. {
  361.     extern char *Baum_String(struct Knoten *,char *);
  362.     *Baum_String(k,s)=0;
  363. }
  364.  
  365. char *Baum_String(struct Knoten *k,char *s)
  366. {
  367.     int kl;
  368.  
  369.     if(k->Operator==OP_NONE) {
  370.         strncpy(s,k->Term,k->Len);
  371.         s+=k->Len;
  372.         return s;
  373.     }
  374.     if(k->Operator>=OP_FUNC1) {
  375.         strncpy(s,k->Term,k->Len);
  376.         s+=k->Len;
  377.         kl=pri_klammer(k,k->r,&s);
  378.         if(!kl) *s++=' ';
  379.         s=Baum_String(k->r,s);
  380.         klammer_zu(&s,kl);
  381.         return s;
  382.     }
  383.     if(k->Operator==OP_NEG) {
  384.         *s++='-';
  385.         kl=pri_klammer(k,k->r,&s);
  386.         s=Baum_String(k->r,s);
  387.         klammer_zu(&s,kl);
  388.         return s;
  389.     }
  390.     kl=pri_klammer(k,k->l,&s);
  391.     if(!kl && k->Operator==OP_POT && k->l->Operator==OP_POT) {
  392.         *s++='(';
  393.         kl=1;
  394.     }
  395.     s=Baum_String(k->l,s);
  396.     klammer_zu(&s,kl);
  397.     *s++=*Op(k->Operator);
  398.     kl=pri_klammer(k,k->r,&s);
  399.     if(!kl && (k->Operator==OP_SUB || k->Operator==OP_DIV) && k->r->Pri==k->Pri) {
  400.         *s++='(';
  401.         kl=1;
  402.     }
  403.     s=Baum_String(k->r,s);
  404.     klammer_zu(&s,kl);
  405.     return s;
  406. }
  407.  
  408.     /*** Einsprung zum Differenzieren
  409.      *** (Term muß korrekt sein)
  410.      ***/
  411.  
  412. void Diff(char *Angabe,char *Ergebnis)
  413. {
  414.     struct Knoten *Root,*d;
  415.  
  416.     Root=Baum_aufbauen(Angabe);
  417.     Baum_zu_String(Root,Ergebnis);
  418.     puts(Ergebnis);
  419.     d=Differenziere(Root);
  420.     Baum_zu_String(d,Ergebnis);
  421.     Baum_abbauen(d);
  422.     Baum_abbauen(Root);
  423. }
  424.  
  425. /* nur ein kurzer Check */
  426.  
  427. Term_korrekt(char *term)
  428. {
  429.     char c,*lastop=NULL,*p=term,*cp=term-1;
  430.     int kl=0;
  431.  
  432.     while((c=*++cp)!=0) if(!isspace(c)) {
  433.         if(strchr("()+-*/^",c)) {
  434.             if(c=='(') kl++;
  435.             else if(c==')') {
  436.                 if(--kl<0 || lastop+1==cp || cp[-1]=='(') return 0;
  437.             }
  438.             else {
  439.                 if(lastop+1==cp || c!='-' && cp[-1]=='(') return 0;
  440.                 lastop=cp;
  441.             }
  442.         }
  443.         else if(!isalnum(c) && c!='.') return 0;
  444.         *p++=c;
  445.     }
  446.     *p=0;
  447.     return kl==0;
  448. }
  449.  
  450. char Angabe[1024],Ergebnis[1024];
  451.  
  452. void main(int argc,char **argv)
  453. {
  454.     if(argc==2 && Term_korrekt(strcpy(Angabe,argv[1]))) {
  455.         Diff(Angabe,Ergebnis);
  456.         puts(Ergebnis);
  457.     }
  458. }
  459.